package com.programmercarl.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/n-queens/description/
 * N皇后问题
 *
 * @author yulongtian
 * @create 2025-01-30 19:53
 */
public class Test14 {
    public static void main(String[] args) {
        Test14 test14 = new Test14();
//        List<String> list = Arrays.asList("..Q.", "Q...", "...Q", ".Q..");
        List<String> list = Arrays.asList("..Q.", "Q...");
        System.out.println(test14.check(list));
        System.out.println();
        System.out.println(test14.solveNQueens(4));
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>(n);
        List<String> path = new ArrayList<>(n);
        backTracking(n, 0, res, path);
        return res;
    }

    public void backTracking(int n, int row, List<List<String>> res, List<String> path) {
        if (row == n && check(path)) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (!check(path)) {
            return;
        }

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            path.add(sb.toString());
            backTracking(n, row + 1, res, path);
            path.remove(path.size() - 1);
        }
    }


    public boolean check(List<String> stringList) {
        if (stringList.isEmpty()) {
            return true;
        }
        // 行
        for (int i = 0; i < stringList.size(); i++) {
            String s = stringList.get(i);
            int count = 0;
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
        }
        // 列
        for (int j = 0; j < stringList.get(0).length(); j++) {
            int count = 0;
            for (int i = 0; i < stringList.size(); i++) {
                String s = stringList.get(i);
                if (s.charAt(j) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
        }
        // 对角线 m行 n列
        int m = stringList.size();
        int n = stringList.get(0).length();
        // 左斜线
        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int p = i, q = 0; p < m && q < n; p++, q++) {
                if (stringList.get(p).charAt(q) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
            count = 0;
            for (int q = i, p = 0; p < m && q < n; q++, p++) {
                if (stringList.get(p).charAt(q) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
        }
        // 右斜线
        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            for (int p = 0, q = i; p < m && q >= 0; p++, q--) {
                if (stringList.get(p).charAt(q) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
            count = 0;
            for (int q = n - 1, p = n - 1 - i; q >= 0 && p < m; q--, p++) {
                if (stringList.get(p).charAt(q) == 'Q') {
                    count++;
                }
                if (count > 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
